home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / common / winding.cpp < prev    next >
C/C++ Source or Header  |  2002-12-08  |  26KB  |  1,101 lines
  1. #include "winding.h"
  2.  
  3. #include "cmdlib.h"
  4. #include "log.h"
  5. #include "mathlib.h"
  6. #include "hlassert.h"
  7.  
  8. #undef BOGUS_RANGE
  9. #undef ON_EPSILON
  10.  
  11. #define    BOGUS_RANGE    10000.0
  12. #define ON_EPSILON 0.01
  13.  
  14. //
  15. // Winding Public Methods
  16. //
  17.  
  18. void            Winding::Print() const
  19. {
  20.     UINT32 x;
  21.  
  22.     for (x=0; x<m_NumPoints; x++)
  23.     {
  24.         Log("(%5.2f, %5.2f, %5.2f)\n", m_Points[x][0], m_Points[x][1], m_Points[x][2]);
  25.     }
  26. }
  27.  
  28. void     Winding::getPlane(dplane_t& plane) const
  29. {
  30.     vec3_t          v1, v2;
  31.     vec3_t          plane_normal;
  32.  
  33.     //hlassert(m_NumPoints >= 3);
  34.  
  35.     if (m_NumPoints >= 3)
  36.     {
  37.         VectorSubtract(m_Points[2], m_Points[1], v1);
  38.         VectorSubtract(m_Points[0], m_Points[1], v2);
  39.  
  40.         CrossProduct(v2, v1, plane_normal);
  41.         VectorNormalize(plane_normal);
  42.         VectorCopy(plane_normal, plane.normal);               // change from vec_t
  43.         plane.dist = DotProduct(m_Points[0], plane.normal);
  44.     }
  45.     else
  46.     {
  47.         VectorClear(plane.normal);
  48.         plane.dist = 0.0;
  49.     }
  50. }
  51.  
  52. void            Winding::getPlane(vec3_t& normal, vec_t& dist) const
  53. {
  54.     vec3_t          v1, v2;
  55.  
  56.     //hlassert(m_NumPoints >= 3);
  57.  
  58.     if (m_NumPoints >= 3)
  59.     {
  60.         VectorSubtract(m_Points[1], m_Points[0], v1);
  61.         VectorSubtract(m_Points[2], m_Points[0], v2);
  62.         CrossProduct(v2, v1, normal);
  63.         VectorNormalize(normal);
  64.         dist = DotProduct(m_Points[0], normal);
  65.     }
  66.     else
  67.     {
  68.         VectorClear(normal);
  69.         dist = 0.0;
  70.     }
  71. }
  72.  
  73. vec_t           Winding::getArea() const
  74. {
  75.     unsigned int    i;
  76.     vec3_t          d1, d2, cross;
  77.     vec_t           total;
  78.  
  79.     //hlassert(m_NumPoints >= 3);
  80.  
  81.     total = 0.0;
  82.     if (m_NumPoints >= 3)
  83.     {
  84.         for (i = 2; i < m_NumPoints; i++)
  85.         {
  86.             VectorSubtract(m_Points[i - 1], m_Points[0], d1);
  87.             VectorSubtract(m_Points[i], m_Points[0], d2);
  88.             CrossProduct(d1, d2, cross);
  89.             total += 0.5 * VectorLength(cross);
  90.         }
  91.     }
  92.     return total;
  93. }
  94.  
  95. void            Winding::getBounds(vec3_t& mins, vec3_t& maxs) const
  96. {
  97.     BoundingBox     bounds;
  98.     unsigned    x;
  99.  
  100.     for (x=0; x<m_NumPoints; x++)
  101.     {
  102.         bounds.add(m_Points[x]);
  103.     }
  104.     VectorCopy(bounds.m_Mins, mins);
  105.     VectorCopy(bounds.m_Maxs, maxs);
  106. }
  107.  
  108. void            Winding::getBounds(BoundingBox& bounds) const
  109. {
  110.     bounds.reset();
  111.     unsigned    x;
  112.  
  113.     for (x=0; x<m_NumPoints; x++)
  114.     {
  115.         bounds.add(m_Points[x]);
  116.     }
  117. }
  118.  
  119. void            Winding::getCenter(vec3_t& center) const
  120. {
  121.     unsigned int    i;
  122.     vec_t           scale;
  123.  
  124.     if (m_NumPoints > 0)
  125.     {
  126.         VectorCopy(vec3_origin, center);
  127.         for (i = 0; i < m_NumPoints; i++)
  128.         {
  129.             VectorAdd(m_Points[i], center, center);
  130.         }
  131.  
  132.         scale = 1.0 / m_NumPoints;
  133.         VectorScale(center, scale, center);
  134.     }
  135.     else
  136.     {
  137.         VectorClear(center);
  138.     }
  139. }
  140.  
  141. Winding*        Winding::Copy() const
  142. {
  143.     Winding* newWinding = new Winding(*this);
  144.     return newWinding;
  145. }
  146.  
  147. void            Winding::Check() const
  148. {
  149.     unsigned int    i, j;
  150.     vec_t*          p1;
  151.     vec_t*          p2;
  152.     vec_t           d, edgedist;
  153.     vec3_t          dir, edgenormal, facenormal;
  154.     vec_t           area;
  155.     vec_t           facedist;
  156.  
  157.     if (m_NumPoints < 3)
  158.     {
  159.         Error("Winding::Check : %i points", m_NumPoints);
  160.     }
  161.  
  162.     area = getArea();
  163.     if (area < 1)
  164.     {
  165.         Error("Winding::Check : %f area", area);
  166.     }
  167.  
  168.     getPlane(facenormal, facedist);
  169.  
  170.     for (i = 0; i < m_NumPoints; i++)
  171.     {
  172.         p1 = m_Points[i];
  173.  
  174.         for (j = 0; j < 3; j++)
  175.         {
  176.             if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
  177.             {
  178.                 Error("Winding::Check : BOGUS_RANGE: %f", p1[j]);
  179.             }
  180.         }
  181.  
  182.         j = i + 1 == m_NumPoints ? 0 : i + 1;
  183.  
  184.         // check the point is on the face plane
  185.         d = DotProduct(p1, facenormal) - facedist;
  186.         if (d < -ON_EPSILON || d > ON_EPSILON)
  187.         {
  188.             Error("Winding::Check : point off plane");
  189.         }
  190.  
  191.         // check the edge isn't degenerate
  192.         p2 = m_Points[j];
  193.         VectorSubtract(p2, p1, dir);
  194.  
  195.         if (VectorLength(dir) < ON_EPSILON)
  196.         {
  197.             Error("Winding::Check : degenerate edge");
  198.         }
  199.  
  200.         CrossProduct(facenormal, dir, edgenormal);
  201.         VectorNormalize(edgenormal);
  202.         edgedist = DotProduct(p1, edgenormal);
  203.         edgedist += ON_EPSILON;
  204.  
  205.         // all other points must be on front side
  206.         for (j = 0; j < m_NumPoints; j++)
  207.         {
  208.             if (j == i)
  209.             {
  210.                 continue;
  211.             }
  212.             d = DotProduct(m_Points[j], edgenormal);
  213.             if (d > edgedist)
  214.             {
  215.                 Error("Winding::Check : non-convex");
  216.             }
  217.         }
  218.     }
  219. }
  220.  
  221. bool          Winding::Valid() const
  222. {
  223.     // TODO: Check to ensure there are 3 non-colinear points
  224.     if ((m_NumPoints < 3) || (!m_Points))
  225.     {
  226.         return false;
  227.     }
  228.     return true;
  229. }
  230.  
  231. //
  232. // Construction
  233. //
  234.  
  235. Winding::Winding()
  236. {
  237.     m_Points = NULL;
  238.     m_NumPoints = m_MaxPoints = 0;
  239. }
  240.  
  241. Winding::Winding(vec3_t *points, UINT32 numpoints)
  242. {
  243.     hlassert(numpoints >= 3);
  244.     m_NumPoints = numpoints;
  245.     m_MaxPoints = (m_NumPoints + 3) & ~3;    // groups of 4
  246.  
  247.     m_Points = new vec3_t[m_MaxPoints];
  248.     memcpy(m_Points, points, sizeof(vec3_t) * m_NumPoints);
  249. }
  250.  
  251. void            Winding::initFromPoints(vec3_t *points, UINT32 numpoints)
  252. {
  253.     hlassert(numpoints >= 3);
  254.  
  255.     Reset();
  256.  
  257.     m_NumPoints = numpoints;
  258.     m_MaxPoints = (m_NumPoints + 3) & ~3;    // groups of 4
  259.  
  260.     m_Points = new vec3_t[m_MaxPoints];
  261.     memcpy(m_Points, points, sizeof(vec3_t) * m_NumPoints);
  262. }
  263.  
  264. Winding&      Winding::operator=(const Winding& other)
  265. {
  266.     delete[] m_Points;
  267.     m_NumPoints = other.m_NumPoints;
  268.     m_MaxPoints = (m_NumPoints + 3) & ~3;   // groups of 4
  269.  
  270.     m_Points = new vec3_t[m_MaxPoints];
  271.     memcpy(m_Points, other.m_Points, sizeof(vec3_t) * m_NumPoints);
  272.     return *this;
  273. }
  274.  
  275.  
  276. Winding::Winding(UINT32 numpoints)
  277. {
  278.     hlassert(numpoints >= 3);
  279.     m_NumPoints = numpoints;
  280.     m_MaxPoints = (m_NumPoints + 3) & ~3;   // groups of 4
  281.  
  282.     m_Points = new vec3_t[m_MaxPoints];
  283.     memset(m_Points, 0, sizeof(vec3_t) * m_NumPoints);
  284. }
  285.  
  286. Winding::Winding(const Winding& other)
  287. {
  288.     m_NumPoints = other.m_NumPoints;
  289.     m_MaxPoints = (m_NumPoints + 3) & ~3;   // groups of 4
  290.  
  291.     m_Points = new vec3_t[m_MaxPoints];
  292.     memcpy(m_Points, other.m_Points, sizeof(vec3_t) * m_NumPoints);
  293. }
  294.  
  295. Winding::~Winding()
  296. {
  297.     delete[] m_Points;
  298. }
  299.  
  300.  
  301. void Winding::initFromPlane(const vec3_t normal, const vec_t dist)
  302. {
  303.     int             i;
  304.     vec_t           max, v;
  305.     vec3_t          org, vright, vup;
  306.  
  307.     // find the major axis               
  308.  
  309.     max = -BOGUS_RANGE;
  310.     int x = -1;
  311.     for (i = 0; i < 3; i++)          
  312.     {
  313.         v = fabs(normal[i]);        
  314.         if (v > max)
  315.         {
  316.             max = v;
  317.             x = i;
  318.         }
  319.     }                
  320.     if (x == -1)
  321.     {
  322.         Error("Winding::initFromPlane no major axis found\n");
  323.     }
  324.  
  325.     VectorCopy(vec3_origin, vup);
  326.     switch (x) 
  327.     {
  328.     case 0:
  329.     case 1:          
  330.         vup[2] = 1;
  331.         break;
  332.     case 2:
  333.         vup[0] = 1;      
  334.         break;
  335.     }
  336.  
  337.     v = DotProduct(vup, normal);
  338.     VectorMA(vup, -v, normal, vup);
  339.     VectorNormalize(vup);
  340.  
  341.     VectorScale(normal, dist, org);
  342.  
  343.     CrossProduct(vup, normal, vright);
  344.  
  345.     VectorScale(vup, BOGUS_RANGE, vup);
  346.     VectorScale(vright, BOGUS_RANGE, vright);
  347.  
  348.     // project a really big     axis aligned box onto the plane
  349.     m_NumPoints = 4;
  350.     m_Points = new vec3_t[m_NumPoints];
  351.  
  352.     VectorSubtract(org, vright, m_Points[0]);
  353.     VectorAdd(m_Points[0], vup, m_Points[0]);
  354.  
  355.     VectorAdd(org, vright, m_Points[1]);
  356.     VectorAdd(m_Points[1], vup, m_Points[1]);
  357.  
  358.     VectorAdd(org, vright, m_Points[2]);
  359.     VectorSubtract(m_Points[2], vup, m_Points[2]);
  360.  
  361.     VectorSubtract(org, vright, m_Points[3]);
  362.     VectorSubtract(m_Points[3], vup, m_Points[3]);
  363. }
  364.  
  365. Winding::Winding(const vec3_t normal, const vec_t dist)
  366. {
  367.     initFromPlane(normal, dist);
  368. }
  369.  
  370. Winding::Winding(const dface_t& face)
  371. {
  372.     int             se;
  373.     dvertex_t*      dv;
  374.     int             v;
  375.  
  376.     m_NumPoints = face.numedges;
  377.     m_Points = new vec3_t[m_NumPoints];
  378.  
  379.     unsigned i;
  380.     for (i = 0; i < face.numedges; i++)
  381.     {
  382.         se = g_dsurfedges[face.firstedge + i];
  383.         if (se < 0)
  384.         {
  385.             v = g_dedges[-se].v[1];
  386.         }
  387.         else
  388.         {
  389.             v = g_dedges[se].v[0];
  390.         }
  391.  
  392.         dv = &g_dvertexes[v];
  393.         VectorCopy(dv->point, m_Points[i]);
  394.     }
  395.  
  396.     RemoveColinearPoints();
  397. }
  398.  
  399. Winding::Winding(const dplane_t& plane)
  400. {
  401.     vec3_t normal;
  402.     vec_t dist;
  403.  
  404.     VectorCopy(plane.normal, normal);
  405.     dist = plane.dist;
  406.     initFromPlane(normal, dist);
  407. }
  408.  
  409. //
  410. // Specialized Functions
  411. //
  412.  
  413. #ifdef COMMON_HULLU
  414. void            Winding::RemoveColinearPoints()
  415. {
  416.     unsigned int    i;
  417.     unsigned int    nump;
  418.     int             j;
  419.     vec3_t          v1, v2;
  420.     vec3_t          p[128];
  421.  
  422.     //JK: Did the optimizations...
  423.  
  424.     if (m_NumPoints>1)
  425.     {
  426.         VectorSubtract(m_Points[0], m_Points[m_NumPoints - 1], v2);
  427.         VectorNormalize(v2);
  428.     }
  429.     nump=0;
  430.     for (i = 0; i < m_NumPoints; i++)
  431.     {
  432.         j = (i + 1) % m_NumPoints;                  // i + 1
  433.  
  434.         VectorSubtract(m_Points[i], m_Points[j], v1);
  435.  
  436.         VectorNormalize(v1);
  437.  
  438.         VectorAdd(v1, v2, v2);
  439.  
  440.         if (!VectorCompare(v2, vec3_origin))
  441.         {
  442.             VectorCopy(m_Points[i], p[nump]);
  443.             nump++;
  444.         }
  445. #if 0
  446.         else
  447.         {
  448.             Log("v3 was (%4.3f %4.3f %4.3f)\n", v2[0], v2[1], v2[2]);
  449.         }
  450. #endif
  451.         //Set v2 for next round
  452.         v2[0]=-v1[0];
  453.         v2[1]=-v1[1];
  454.         v2[2]=-v1[2];
  455.     }
  456.  
  457.     if (nump == m_NumPoints)
  458.     {
  459.         return;  
  460.     }
  461.  
  462. #if 0
  463.     Warning("RemoveColinearPoints: Removed %u points, from %u to %u\n", m_NumPoints - nump, m_NumPoints, nump);
  464.     Warning("Before :\n");
  465.     Print();
  466. #endif
  467.     m_NumPoints = nump;
  468.     memcpy(m_Points, p, nump * sizeof(vec3_t));
  469.  
  470. #if 0
  471.     Warning("After :\n");
  472.     Print();
  473.  
  474.     Warning("==========\n");
  475. #endif
  476. }
  477.  
  478.  
  479. #else /*COMMON_HULLU*/
  480.  
  481.  
  482. void            Winding::RemoveColinearPoints()
  483. {
  484.     unsigned int    i;
  485.     unsigned int    nump;
  486.     int             j, k;
  487.     vec3_t          v1, v2, v3;
  488.     vec3_t          p[128];
  489.  
  490.     // TODO: OPTIMIZE:  this could be 1/2 the number of vectornormalize calls by caching one of the previous values through the loop
  491.     // TODO: OPTIMIZE: Remove the modulo operations inside the loop and replace with compares
  492.     nump = 0;
  493.     for (i = 0; i < m_NumPoints; i++)
  494.     {
  495.         j = (i + 1) % m_NumPoints;                  // i + 1
  496.         k = (i + m_NumPoints - 1) % m_NumPoints;    // i - 1 
  497.         VectorSubtract(m_Points[i], m_Points[j], v1);
  498.         VectorSubtract(m_Points[i], m_Points[k], v2);
  499.         VectorNormalize(v1);
  500.         VectorNormalize(v2);
  501.         VectorAdd(v1, v2, v3);
  502.         if (!VectorCompare(v3, vec3_origin))
  503.         {
  504.             VectorCopy(m_Points[i], p[nump]);
  505.             nump++;
  506.         }
  507. #if 0
  508.         else
  509.         {
  510.             Log("v3 was (%4.3f %4.3f %4.3f)\n", v3[0], v3[1], v3[2]);
  511.         }
  512. #endif
  513.     }
  514.  
  515.     if (nump == m_NumPoints)
  516.     {
  517.         return;  
  518.     }
  519.  
  520. #if 0
  521.     Warning("RemoveColinearPoints: Removed %u points, from %u to %u\n", m_NumPoints - nump, m_NumPoints, nump);
  522.     Warning("Before :\n");
  523.     Print();
  524. #endif
  525.     m_NumPoints = nump;
  526.     memcpy(m_Points, p, nump * sizeof(vec3_t));
  527.  
  528. #if 0
  529.     Warning("After :\n");
  530.     Print();
  531.  
  532.     Warning("==========\n");
  533. #endif
  534. }
  535.  
  536. #endif /*!COMMON_HULLU*/
  537.  
  538.  
  539. void            Winding::Clip(const dplane_t& plane, Winding** front, Winding** back)
  540. {
  541.     vec3_t normal;
  542.     vec_t dist;
  543.     VectorCopy(plane.normal, normal);
  544.     dist = plane.dist;
  545.     Clip(normal, dist, front, back);
  546. }
  547.  
  548.  
  549. void            Winding::Clip(const vec3_t normal, const vec_t dist, Winding** front, Winding** back)
  550. {
  551.     vec_t           dists[MAX_POINTS_ON_WINDING + 4];
  552.     int             sides[MAX_POINTS_ON_WINDING + 4];
  553.     int             counts[3];
  554.     vec_t           dot;
  555.     unsigned int    i, j;
  556.     unsigned int    maxpts;
  557.  
  558.     counts[0] = counts[1] = counts[2] = 0;
  559.  
  560.     // determine sides for each point
  561.     for (i = 0; i < m_NumPoints; i++)
  562.     {
  563.         dot = DotProduct(m_Points[i], normal);
  564.         dot -= dist;
  565.         dists[i] = dot;
  566.         if (dot > ON_EPSILON)
  567.         {
  568.             sides[i] = SIDE_FRONT;
  569.         }
  570.         else if (dot < -ON_EPSILON)
  571.         {
  572.             sides[i] = SIDE_BACK;
  573.         }
  574.         else
  575.         {
  576.             sides[i] = SIDE_ON;
  577.         }
  578.         counts[sides[i]]++;
  579.     }
  580.     sides[i] = sides[0];
  581.     dists[i] = dists[0];
  582.  
  583.     if (!counts[0])
  584.     {
  585.         *front = NULL;
  586.         *back = new Winding(*this);
  587.         return;
  588.     }
  589.     if (!counts[1])
  590.     {
  591.         *front = new Winding(*this);
  592.         *back = NULL;
  593.         return;
  594.     }
  595.  
  596.     maxpts = m_NumPoints + 4;                            // can't use counts[0]+2 because
  597.     // of fp grouping errors
  598.  
  599.     Winding* f = new Winding(maxpts);
  600.     Winding* b = new Winding(maxpts);
  601.  
  602.     *front = f;
  603.     *back = b;
  604.  
  605.     f->m_NumPoints = 0;
  606.     b->m_NumPoints = 0;
  607.  
  608.     for (i = 0; i < m_NumPoints; i++)
  609.     {
  610.         vec_t* p1 = m_Points[i];
  611.  
  612.         if (sides[i] == SIDE_ON)
  613.         {
  614.             VectorCopy(p1, f->m_Points[f->m_NumPoints]);
  615.             VectorCopy(p1, b->m_Points[b->m_NumPoints]);
  616.             f->m_NumPoints++;
  617.             b->m_NumPoints++;
  618.             continue;
  619.         }
  620.         else if (sides[i] == SIDE_FRONT)
  621.         {
  622.             VectorCopy(p1, f->m_Points[f->m_NumPoints]);
  623.             f->m_NumPoints++;
  624.         }
  625.         else if (sides[i] == SIDE_BACK)
  626.         {
  627.             VectorCopy(p1, b->m_Points[b->m_NumPoints]);
  628.             b->m_NumPoints++;
  629.         }
  630.  
  631.         if ((sides[i + 1] == SIDE_ON) | (sides[i + 1] == sides[i]))  // | instead of || for branch optimization
  632.         {
  633.             continue;
  634.         }
  635.  
  636.         // generate a split point
  637.         vec3_t mid;
  638.         unsigned int tmp = i + 1;
  639.         if (tmp >= m_NumPoints)
  640.         {
  641.             tmp = 0;
  642.         }
  643.         vec_t* p2 = m_Points[tmp];
  644.         dot = dists[i] / (dists[i] - dists[i + 1]);
  645. #if 0
  646.         for (j = 0; j < 3; j++)
  647.         {                                                  // avoid round off error when possible
  648.             if (normal[j] < 1.0 - NORMAL_EPSILON)
  649.             {
  650.                 if (normal[j] > -1.0 + NORMAL_EPSILON)
  651.                 {
  652.                     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  653.                 }
  654.                 else
  655.                 {
  656.                     mid[j] = -dist;
  657.                 }
  658.             }
  659.             else
  660.             {
  661.                 mid[j] = dist;
  662.             }
  663.         }
  664. #else
  665.         for (j = 0; j < 3; j++)
  666.         {                                                  // avoid round off error when possible
  667.             if (normal[j] == 1)
  668.                 mid[j] = dist;
  669.             else if (normal[j] == -1)
  670.                 mid[j] = -dist;
  671.             else
  672.                 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  673.         }
  674. #endif
  675.  
  676.         VectorCopy(mid, f->m_Points[f->m_NumPoints]);
  677.         VectorCopy(mid, b->m_Points[b->m_NumPoints]);
  678.         f->m_NumPoints++;
  679.         b->m_NumPoints++;
  680.     }
  681.  
  682.     if ((f->m_NumPoints > maxpts) | (b->m_NumPoints > maxpts)) // | instead of || for branch optimization
  683.     {
  684.         Error("Winding::Clip : points exceeded estimate");
  685.     }
  686.     if ((f->m_NumPoints > MAX_POINTS_ON_WINDING) | (b->m_NumPoints > MAX_POINTS_ON_WINDING)) // | instead of || for branch optimization
  687.     {
  688.         Error("Winding::Clip : MAX_POINTS_ON_WINDING");
  689.     }
  690.     f->RemoveColinearPoints();
  691.     b->RemoveColinearPoints();
  692. }
  693.  
  694. bool          Winding::Chop(const vec3_t normal, const vec_t dist)
  695. {
  696.     Winding*      f;
  697.     Winding*      b;
  698.  
  699.     Clip(normal, dist, &f, &b);
  700.     if (b)
  701.     {
  702.         delete b;
  703.     }
  704.  
  705.     if (f)
  706.     {
  707.         delete[] m_Points;
  708.         m_NumPoints = f->m_NumPoints;
  709.         m_Points = f->m_Points;
  710.         f->m_Points = NULL;
  711.         delete f;
  712.         return true;
  713.     }
  714.     else
  715.     {
  716.         m_NumPoints = 0;
  717.         delete[] m_Points;
  718.         m_Points = NULL;
  719.         return false;
  720.     }
  721. }
  722.  
  723. int             Winding::WindingOnPlaneSide(const vec3_t normal, const vec_t dist)
  724. {
  725.     bool            front, back;
  726.     unsigned int    i;
  727.     vec_t           d;
  728.  
  729.     front = false;
  730.     back = false;
  731.     for (i = 0; i < m_NumPoints; i++)
  732.     {
  733.         d = DotProduct(m_Points[i], normal) - dist;
  734.         if (d < -ON_EPSILON)
  735.         {
  736.             if (front)
  737.             {
  738.                 return SIDE_CROSS;
  739.             }
  740.             back = true;
  741.             continue;
  742.         }
  743.         if (d > ON_EPSILON)
  744.         {
  745.             if (back)
  746.             {
  747.                 return SIDE_CROSS;
  748.             }
  749.             front = true;
  750.             continue;
  751.         }
  752.     }
  753.  
  754.     if (back)
  755.     {
  756.         return SIDE_BACK;
  757.     }
  758.     if (front)
  759.     {
  760.         return SIDE_FRONT;
  761.     }
  762.     return SIDE_ON;
  763. }
  764.  
  765.  
  766. bool Winding::Clip(const dplane_t& split, bool keepon)
  767. {
  768.     vec_t           dists[MAX_POINTS_ON_WINDING];
  769.     int             sides[MAX_POINTS_ON_WINDING];
  770.     int             counts[3];
  771.     vec_t           dot;
  772.     int             i, j;
  773.  
  774.     counts[0] = counts[1] = counts[2] = 0;
  775.  
  776.     // determine sides for each point
  777.     // do this exactly, with no epsilon so tiny portals still work
  778.     for (i = 0; i < m_NumPoints; i++)
  779.     {
  780.         dot = DotProduct(m_Points[i], split.normal);
  781.         dot -= split.dist;
  782.         dists[i] = dot;
  783.         if (dot > ON_EPSILON)
  784.         {
  785.             sides[i] = SIDE_FRONT;
  786.         }
  787.         else if (dot < ON_EPSILON)
  788.         {
  789.             sides[i] = SIDE_BACK;
  790.         }
  791.         else
  792.         {
  793.             sides[i] = SIDE_ON;
  794.         }
  795.         counts[sides[i]]++;
  796.     }
  797.     sides[i] = sides[0];
  798.     dists[i] = dists[0];
  799.  
  800.     if (keepon && !counts[0] && !counts[1])
  801.     {
  802.         return true;
  803.     }
  804.  
  805.     if (!counts[0])
  806.     {
  807.         delete[] m_Points;
  808.         m_Points = NULL;
  809.         m_NumPoints = 0;
  810.         return false;
  811.     }
  812.  
  813.     if (!counts[1])
  814.     {
  815.         return true;
  816.     }
  817.  
  818.     unsigned maxpts = m_NumPoints + 4;                            // can't use counts[0]+2 because of fp grouping errors
  819.     unsigned newNumPoints = 0;
  820.     vec3_t* newPoints = new vec3_t[maxpts];
  821.     memset(newPoints, 0, sizeof(vec3_t) * maxpts);
  822.  
  823.     for (i = 0; i < m_NumPoints; i++)
  824.     {
  825.         vec_t* p1 = m_Points[i];
  826.  
  827.         if (sides[i] == SIDE_ON)
  828.         {
  829.             VectorCopy(p1, newPoints[newNumPoints]);
  830.             newNumPoints++;
  831.             continue;
  832.         }
  833.         else if (sides[i] == SIDE_FRONT)
  834.         {
  835.             VectorCopy(p1, newPoints[newNumPoints]);
  836.             newNumPoints++;
  837.         }
  838.  
  839.         if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  840.         {
  841.             continue;
  842.         }
  843.  
  844.         // generate a split point
  845.         vec3_t mid;
  846.         unsigned int tmp = i + 1;
  847.         if (tmp >= m_NumPoints)
  848.         {
  849.             tmp = 0;
  850.         }
  851.         vec_t* p2 = m_Points[tmp];
  852.         dot = dists[i] / (dists[i] - dists[i + 1]);
  853.         for (j = 0; j < 3; j++)
  854.         {                                                  // avoid round off error when possible
  855.             if (split.normal[j] < 1.0 - NORMAL_EPSILON)
  856.             {
  857.                 if (split.normal[j] > -1.0 + NORMAL_EPSILON)
  858.                 {
  859.                     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  860.                 }
  861.                 else
  862.                 {
  863.                     mid[j] = -split.dist;
  864.                 }
  865.             }
  866.             else
  867.             {
  868.                 mid[j] = split.dist;
  869.             }
  870.         }
  871.  
  872.         VectorCopy(mid, newPoints[newNumPoints]);
  873.         newNumPoints++;
  874.     }
  875.  
  876.     if (newNumPoints > maxpts)
  877.     {
  878.         Error("Winding::Clip : points exceeded estimate");
  879.     }
  880.  
  881.     delete[] m_Points;
  882.     m_Points = newPoints;
  883.     m_NumPoints = newNumPoints;
  884.  
  885.     RemoveColinearPoints();
  886.  
  887.     return true;
  888. }
  889.  
  890. /*
  891.  * ==================
  892.  * Divide
  893.  * Divides a winding by a plane, producing one or two windings.  The
  894.  * original winding is not damaged or freed.  If only on one side, the
  895.  * returned winding will be the input winding.  If on both sides, two
  896.  * new windings will be created.
  897.  * ==================
  898.  */
  899.  
  900. void Winding::Divide(const dplane_t& split, Winding** front, Winding** back)
  901. {
  902.     vec_t           dists[MAX_POINTS_ON_WINDING];
  903.     int             sides[MAX_POINTS_ON_WINDING];
  904.     int             counts[3];
  905.     vec_t           dot;
  906.     int             i, j;
  907.     int             maxpts;
  908.  
  909.     counts[0] = counts[1] = counts[2] = 0;
  910.  
  911.     // determine sides for each point
  912.     for (i = 0; i < m_NumPoints; i++)
  913.     {
  914.         dot = DotProduct(m_Points[i], split.normal);
  915.         dot -= split.dist;
  916.         dists[i] = dot;
  917.         if (dot > ON_EPSILON)
  918.         {
  919.             sides[i] = SIDE_FRONT;
  920.         }
  921.         else if (dot < -ON_EPSILON)
  922.         {
  923.             sides[i] = SIDE_BACK;
  924.         }
  925.         else
  926.         {
  927.             sides[i] = SIDE_ON;
  928.         }
  929.         counts[sides[i]]++;
  930.     }
  931.     sides[i] = sides[0];
  932.     dists[i] = dists[0];
  933.  
  934.     *front = *back = NULL;
  935.  
  936.     if (!counts[0])
  937.     {
  938.         *back = this;   // Makes this function non-const
  939.         return;
  940.     }
  941.     if (!counts[1])
  942.     {
  943.         *front = this;  // Makes this function non-const
  944.         return;
  945.     }
  946.  
  947.     maxpts = m_NumPoints + 4;                            // can't use counts[0]+2 because
  948.     // of fp grouping errors
  949.  
  950.     Winding* f = new Winding(maxpts);
  951.     Winding* b = new Winding(maxpts);
  952.  
  953.     *front = f;
  954.     *back = b;
  955.  
  956.     f->m_NumPoints = 0;
  957.     b->m_NumPoints = 0;
  958.  
  959.     for (i = 0; i < m_NumPoints; i++)
  960.     {
  961.         vec_t* p1 = m_Points[i];
  962.  
  963.         if (sides[i] == SIDE_ON)
  964.         {
  965.             VectorCopy(p1, f->m_Points[f->m_NumPoints]);
  966.             VectorCopy(p1, b->m_Points[b->m_NumPoints]);
  967.             f->m_NumPoints++;
  968.             b->m_NumPoints++;
  969.             continue;
  970.         }
  971.         else if (sides[i] == SIDE_FRONT)
  972.         {
  973.             VectorCopy(p1, f->m_Points[f->m_NumPoints]);
  974.             f->m_NumPoints++;
  975.         }
  976.         else if (sides[i] == SIDE_BACK)
  977.         {
  978.             VectorCopy(p1, b->m_Points[b->m_NumPoints]);
  979.             b->m_NumPoints++;
  980.         }
  981.  
  982.         if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  983.         {
  984.             continue;
  985.         }
  986.  
  987.         // generate a split point
  988.         vec3_t mid;
  989.         unsigned int tmp = i + 1;
  990.         if (tmp >= m_NumPoints)
  991.         {
  992.             tmp = 0;
  993.         }
  994.         vec_t* p2 = m_Points[tmp];
  995.         dot = dists[i] / (dists[i] - dists[i + 1]);
  996.         for (j = 0; j < 3; j++)
  997.         {                                                  // avoid round off error when possible
  998.             if (split.normal[j] < 1.0 - NORMAL_EPSILON)
  999.             {
  1000.                 if (split.normal[j] > -1.0 + NORMAL_EPSILON)
  1001.                 {
  1002.                     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  1003.                 }
  1004.                 else
  1005.                 {
  1006.                     mid[j] = -split.dist;
  1007.                 }
  1008.             }
  1009.             else
  1010.             {
  1011.                 mid[j] = split.dist;
  1012.             }
  1013.         }
  1014.  
  1015.         VectorCopy(mid, f->m_Points[f->m_NumPoints]);
  1016.         VectorCopy(mid, b->m_Points[b->m_NumPoints]);
  1017.         f->m_NumPoints++;
  1018.         b->m_NumPoints++;
  1019.     }
  1020.  
  1021.     if (f->m_NumPoints > maxpts || b->m_NumPoints > maxpts)
  1022.     {
  1023.         Error("Winding::Divide : points exceeded estimate");
  1024.     }
  1025.  
  1026.     f->RemoveColinearPoints();
  1027.     b->RemoveColinearPoints();
  1028. }
  1029.  
  1030.  
  1031. void            Winding::addPoint(const vec3_t newpoint)
  1032. {
  1033.     if (m_NumPoints >= m_MaxPoints)
  1034.     {
  1035.         resize(m_NumPoints + 1);
  1036.     }
  1037.     VectorCopy(newpoint, m_Points[m_NumPoints]);
  1038.     m_NumPoints++;
  1039. }
  1040.  
  1041.  
  1042. void            Winding::insertPoint(const vec3_t newpoint, const unsigned int offset)
  1043. {
  1044.     if (offset >= m_NumPoints)
  1045.     {
  1046.         addPoint(newpoint);
  1047.     }
  1048.     else
  1049.     {
  1050.         if (m_NumPoints >= m_MaxPoints)
  1051.         {
  1052.             resize(m_NumPoints + 1);
  1053.         }
  1054.  
  1055.         unsigned x;
  1056.         for (x = m_NumPoints; x>offset; x--)
  1057.         {
  1058.             VectorCopy(m_Points[x-1], m_Points[x]);
  1059.         }
  1060.         VectorCopy(newpoint, m_Points[x]);
  1061.  
  1062.         m_NumPoints++;
  1063.     }
  1064. }
  1065.  
  1066.  
  1067. void            Winding::resize(UINT32 newsize)
  1068. {
  1069.     newsize = (newsize + 3) & ~3;   // groups of 4
  1070.  
  1071.     vec3_t* newpoints = new vec3_t[newsize];
  1072.     m_NumPoints = min(newsize, m_NumPoints);
  1073.     memcpy(newpoints, m_Points, m_NumPoints);
  1074.     delete[] m_Points;
  1075.     m_Points = newpoints;
  1076.     m_MaxPoints = newsize;
  1077. }
  1078.  
  1079. void            Winding::CopyPoints(vec3_t *points, int &numpoints)
  1080. {
  1081.     if(!points)
  1082.     {
  1083.         numpoints = 0;
  1084.         return;
  1085.     }
  1086.  
  1087.     memcpy(points, m_Points, sizeof(vec3_t) * m_NumPoints);
  1088.  
  1089.     numpoints = m_NumPoints;
  1090. }
  1091.  
  1092. void            Winding::Reset(void)
  1093. {
  1094.     if(m_Points)
  1095.     {
  1096.         delete [] m_Points;
  1097.         m_Points = NULL;
  1098.     }
  1099.  
  1100.     m_NumPoints = m_MaxPoints = 0;
  1101. }